package com.xy6.algo.search;

/**
 * 插值查找
 * <p>时间复杂度：O(log2^(log2^n))
 * <p>适合表长比较大，关键字分布均匀的查找表
 * 
 * <pre>
 * 二分查找的演化算法。
 * 二分查找步长为1/2，插值查找步长自适应。
 * 
 * 取集合首元素min、尾元素max，与目标元素x比较；
 * 如果x不在min-max范围内，或等于min或max，则查找结束；
 * 否则，计算中间元素mid=min+(max-x)/(x-min)，比较mid元素与x大小；
 * 如果与x相等，则查找结束；
 * 如果比x小，则min=mid+1，max=max-1；
 * 如果比x大，则min=min+1，max=mid-1；
 * 如果x等于min或max，则查找结束；
 * 否则，计算中间元素mid，计算规则同上。
 * 重复上述步骤，直至找到元素，或者min>=max，查找结束。
 * </pre>
 * 
 * @author zhang
 * @since 2017-08-04
 */
public class SearchInsert {

	public static void main(String[] args) {
		Integer[] arr = new Integer[] { 1, 2, 3, 5, 10, 50, 100 };
		search(arr, 6);
	}

	public static void search(Integer[] arr, int val) {
		int index = search(arr, val, 0, arr.length - 1);
		System.err.println(index);
	}

	public static int search(Integer[] arr, int val, int low, int high) {
		if(low >= high){
			return -1;
		}
		
		int mid = low + (val - arr[low]) / (arr[high] - arr[low]);
		System.out.println(String.format("%d", mid));
		if(arr[mid] > val){
			return search(arr, val, low, mid-1);
		} else if(arr[mid] == val){
			return mid;
		} else {
			return search(arr, val, low+1, high);
		}
	}

}
